357. Позвольте посчитать количество

 

В наличии имеются 5 номиналов монет: 50, 25, 10, 5 и 1 центовые. Сколькими способами можно разменять заданную сумму s?

 

Вход. Каждая строка содержит сумму s от 0 до 30000 включительно.

 

Выход. Для каждого теста вывести в отдельной строке количество способов, которыми можно разменять s центов в соответствии со следующим форматом:

Если существует m вариантов размена (m > 1), то вывести фразу: There are m ways to produce s cents change.

Если существует единственный вариант размена, то вывести фразу: There is only 1 way to produce s cents change.

 

Пример входа

17
11
4
 

Пример выхода

There are 6 ways to produce 17 cents change. 
There are 4 ways to produce 11 cents change. 
There is only 1 way to produce 4 cents change.
 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Обозначим через f(k, n) количество способов составить сумму n из первых k номиналов монет. Оно равно количеству способов составить сумму n первыми (k – 1) номиналами плюс количество способов составить сумму (n – ak) k номиналами. Имеем соотношение:

f(k, n) = f(k – 1, n) + f(k, n – ak)

 

k \ n

 

 

 

 

 

 

 

 

f[k - 1, n]

 

 

f[k, n – ak]

 

 

f[k, n]

 

 

 

 

 

 

 

 

Изначально положим f(0, 0) = 1, f(n, 0) = 0, n > 0.

 

Пример

11 центов можно разменять 4 способами:

1)      10 + 1

2)      5 + 5 + 1

3)      5 + 1 + 1 + 1 + 1 + 1 + 1

4)      1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

 

 

k \ n

0

1

2

3

4

5

6

7

8

9

10

11

начало

0

1

0

0

0

0

0

0

0

0

0

0

0

c = 1

1

1

1

1

1

1

1

1

1

1

1

1

1

c = 5

2

1

1

1

1

1

2

2

2

2

2

3

3

c = 10

3

1

1

1

1

1

2

2

2

2

2

4

4

 

Номиналы в 25 и 50 центов не повлияют на результат для 11 центов.

 

Реализация алгоритма

Поскольку сумма s ограничена значением 30000, то количество способов ее разбиения может не входить в 32-битовый тип. Воспользуемся 64-битовым типом данных long long (GNU C). Для Visual C следует использовать тип __int64.

Ячейка mas[i] будет содержать количество способов, которыми можно выдать сумму i. Размер массива установим MAX = 30001. Номиналы монет занесем в массив coins.

 

const int MAX = 30001;

long long mas[MAX];

int coins[5] = {1, 5, 10, 20, 50};

 

Динамически пересчитываем массив mas для каждого номинала (всего 5 циклов) согласно выше приведенному соотношению.

 

  memset(mas,0,sizeof(mas)); mas[0] = 1;

  for(i = 0; i < 5; i++)

  {

    for(j = coins[i]; j < MAX; j++)

      mas[j] += mas[j - coins[i]];

  }

 

Читаем входные суммы и печатаем результат.

 

  while(scanf("%d",&n) == 1)

    if (mas[n] > 1) printf("There are %lld ways to produce %d cents

        change.\n",mas[n],n);

    else printf("There is only 1 way to produce %d cents change.\n",n);